# 矩阵置零：https://leetcode-cn.com/problems/set-matrix-zeroes/submissions/

# m + n空间复杂度
class Solution:
    def setZeroes(self, matrix) -> None:
        """
        这道题的 可以使用一个一样大小的新m x n的列表来做
        这里升级一下使用 一个m， 一个 n长度的数组来做。 数组对应的是计算该位置的行列是否需要置零
        空间复杂度 n +m， 时间复杂度n x m + n + m ,减少了空间复杂度
        """
        # n 记录行数。 m 记录列数
        n, m = len(matrix), len(matrix[0])
        row_n = [False]*n
        col_m = [False]*m
        for row in range(n):
            for col in range(m):
                if matrix[row][col] == 0:
                    row_n[row] = True
                    col_m[col] = True

        # 优化双循环写法,行列任意为 True，则可将其置为0
        for row in range(n):
            for col in range(m):
                if row_n[row] or col_m[col]:
                    matrix[row][col] = 0
        """
        for row, value in enumerate(row_n):
            if value: 
                for i in range(m):
                    matrix[row][i] = 0
        for col, value in enumerate(col_m):
            if value:
                for i in range(n):
                    matrix[i][col] = 0
        """

# 只用两个标志符，O(1) 空间复杂度解决
class Solution:
    def setZeroes(self, matrix) -> None:
        """
            根据 n + m空间复杂度的思想，实际上就是使用了另外两个数组来记录行和列是否置零。 那么也可以直接使用 原来矩阵的第一行，第一列来记录信息。
        """
        # n 记录行数。 m 记录列数
        n, m = len(matrix), len(matrix[0])

        # 添加标识, 要确定的是原矩阵，第一行第一列是否有0，才能将第一行或者第一列置零
        row1_flag = False
        col1_flag = False
        for i in range(n):
            if matrix[i][0] == 0:
                col1_flag = True
                break
        for j in range(m):
            if matrix[0][j] == 0:
                row1_flag = True
                break

        for row in range(n):
            for col in range(m):
                if not matrix[row][col]:
                    # 将其对应的行和列都置为0，用来记录该行列是否需要置为零
                    matrix[0][col] = 0
                    matrix[row][0] = 0

        # 开始根据信息置零: 这里有个小问题， 因为第一行第一列作为存放信息使用。 所以，不可先改变第一行第一列的值， 假如将不该为0的第一行内元素置为0了， 那么以他为参照的后序 行列都将置0就会出错。
        """
        以这个为例子， 交换为信息后，还是这样。 但先把 1， 2换为0后，下面的 4, 5  3, 1也全部为0！ 这是错的。
        所以需要先更新后面的，再回头更新 第一行，第一列。  需要添加标识，判断第一行，第一列是否需要置为零
            [
                [0,1,2,0],
                [3,4,5,2],
                [1,3,1,5]
            ]
        """

        # 从1开始
        for row in range(1, n):
            for col in range(1, m):
                if matrix[0][col] == 0 or matrix[row][0] == 0:
                    matrix[row][col] = 0
        
        if col1_flag: 
            for i in range(n):
                matrix[i][0] = 0
                
        if row1_flag:
            for j in range(m):
                matrix[0][j] = 0
                    


"""
[
 [1,1,1],
 [1,0,1],
 [1,1,1]
]


[
    [1, 0, 1], 
    [0, 0, 1], 
    [1, 1, 1]
]

[
    [0,0,1],
    [0,0,0],
    [0,0,1]]


[
    [0,1,2,0],
    [3,4,5,2],
    [1,3,1,5]
]


[
    [0,1,2,0],
    [0,4,5,0],
    [0,3,1,0]
]

"""

